package WeeklyContest.Bi.B31;

import java.util.HashMap;
import java.util.Map;

public class B31 {
  
}

//5457. 和为奇数的子数组数目   

/** 
 * 没必要写成dp
 * 记录odd 和 even 的个数累加即可
 * 
*/

//超时  解法 dp表示当前总共有多少种
// class Solution {
//     public int numOfSubarrays(int[] arr) {
//         int mod = (int)1e9+7;
//         int n = arr.length;
//         int[] dp = new int[n];
//         int[] preSum = new int[n];
//         dp[0] = arr[0]%2;
//         preSum[0]=arr[0];
//         for (int i = 1; i < preSum.length; i++) {
//             preSum[i] = preSum[i-1]+arr[i];
//         }
//         for (int i = 1; i < dp.length; i++) {
//             int t = preSum[i];
//             int cur = t%2;
//             for (int j = 0; j < i; j++) {
//                 if((t-preSum[j])%2==1) {
//                     cur++;
//                     cur%=mod;
//                 }
//             }
//             dp[i]=(dp[i-1]+cur)%mod;
//         }
//         return dp[n-1];
//     }   
// }

//o n 复杂度的解法 dp表示以当前元素结尾的有多少种 ,利用奇偶 进行计算
// class Solution {
//     public int numOfSubarrays(int[] arr) {
//         int mod = (int)1e9+7;
//         int n = arr.length;
//         int[] dp = new int[n];
//         dp[0]=arr[0]&1;
//         for (int i = 1; i < dp.length; i++) {
//             if(0==(arr[i]&1)){ //偶数
//                 dp[i]=dp[i-1];
//             }
//             else{
//                 dp[i]=1;
//                 int even = i - dp[i-1];
//                 dp[i]+=even; 
                
//             }
//         }
//         int ans =0;
//         for (int i : dp) {
//             ans+=i;
//             ans%=mod;
//         }
//         return ans;
//     }
// }




//5458. 字符串的好分割数目
// class Solution {
//     public int numSplits(String s) {
//         int ans=0;
//         Map<Character,Integer> mapL = new HashMap<>(); 
//         Map<Character,Integer> mapR = new HashMap<>(); 

//         for (char c : s.toCharArray()) {
//             mapR.put(c, mapR.getOrDefault(c, 0)+1);
//         }

//         for (int i = 0; i < s.length(); i++) {
//             char cur = s.charAt(i);
//             mapL.put(cur, mapL.getOrDefault(cur, 0)+1);
//             int n = mapR.getOrDefault(cur, 0);
//             if(n==1) mapR.remove(cur);
//             else mapR.put(cur, n-1);
//             if(mapL.keySet().size()==mapR.keySet().size()) ans++;
//         }
//         return ans;
//     }
// }



//5459. 形成目标数组的子数组最少增加次数  

//超时解法
class Solution_Five {
    public int minNumberOperations(int[] target) {
        int ans =0;
        while(!isZero(target)){
            int start = findStart(target);
            int next = findNext(target, start);
            
            for (int i = start; i <=next ; i++) {
                ;
            }
        }
        return ans;
    }

    public int findStart(int[] tar){
        for (int i = 0; i < tar.length; i++) {
            if(tar[i]!=0) return i;
        }
        return -1;
    }

    public int findNext(int[] tar,int index){
        for (int i = index+1; i < tar.length; i++) {
            if(tar[i]==0) return i-1;
        }
        return tar.length-1;
    }

    public boolean isZero(int[] tar){
        for (int i : tar) {
            if(i!=0) return false;
        }
        return true;
    }
}


class Solution {
    public int minNumberOperations(int[] target) {

        int n = target.length;
        int ans = target[0];
        for (int i = 1; i < n; ++i) {
            ans += Math.max(target[i] - target[i - 1], 0);
        }
        return ans;

    }
}

